package letter_combinations_of_a_phone_number

//建立数字与字母的映射
var letterMap = []string{
	"",
	"",
	"abc",
	"def",
	"ghi",
	"jkl",
	"mno",
	"pqrs",
	"tuv",
	"wxyz",
}
//存储结果的切片
/*
求给出数字对应的字符串组合
首先想到暴力，一层一层遍历，一个数字一次遍历，但是无法确定有多少个数字，也就不能确定有多少层
回溯算法：
1：每次得到一个数字，将数字映射到字符串。
2：根据字符串中的每个字母进行递归，每次递归将递归层数+1，当层数=数字字符串的长度时，就将字符串填入结果切片中。
 */
var res = make([]string, 0)
func LetterCombinations(digits string) []string {
	//如果字符串为空，直接返回
	if digits == "" {
		return res
	}
	res = []string{}
	//进行首次调用递归
	findcombination(&digits, 0, "")
	return res
}
//递归
func findcombination(digits *string, index int, s string) {
	//判断递归层数是否和字符串长度相等，如果相等，将字符串放入切片
	if index == len(*digits) {
		res = append(res, s)
		return
	}
	//取数字所对应的字符串
	letter := letterMap[(*digits)[index]-'0']
	//遍历字符串，在原始的基础上加上此数对应的字符串
	for i := 0; i < len(letter); i++ {
		findcombination(digits, index+1, s+string(letter[i]))
	}
	return
}
